# coding=utf-8
r"""
Words of all kinds

AUTHORS:
    -- Arnaud Bergeron
    -- Amy Glen
    -- Sébastien Labbé
    -- Franco Saliola
    
EXAMPLES:
We define the set of words over 'a' and 'b'.
    sage: W = Words('ab'); W
    Words over {'a', 'b'}
    
Then we can build some words in the set:
    sage: W('abba')
    word: abba
    
If you try to use symbols that are not the alphabet of the set you get an error:
    sage: W([1, 2])
    Traceback (most recent call last):
    ...
    IndexError: symbol not in alphabet: 1
    
You can also build infinite words backed by a function or an iterator!
    sage: def f(n):
    ...     if n % 2 == 1:
    ...         return 'a'
    ...     else:
    ...         return 'b'
    ...
    sage: W(f)
    Infinite word over {'a', 'b'}
"""
#*****************************************************************************
#       Copyright (C) 2008 Arnaud bergeron <abergeron@gmail.com>,
#                          Amy Glen <amy.glen@gmail.com>,       
#                          Sébastien Labbé <slabqc@gmail.com>,
#                          Franco Saliola <saliola@gmail.com>,
#
#  Distributed under the terms of the GNU General Public License version 2 (GPLv2)
#
#  The full text of the GPLv2 is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from array import array
from itertools import tee, islice, ifilter, ifilterfalse, imap, izip, \
                      starmap, count, repeat, dropwhile, chain, cycle
from weakref import WeakValueDictionary
from sage.structure.sage_object import SageObject
from sage.rings.infinity import infinity
from sage.misc.latex import latex
from sage.words.alpha import Alphabet
from sage.words.disjoint_set import DisjointSet
from sage.words.utils import *

def Word(word=None, alphabet=None):
    r"""
    Returns a FiniteWord object over the given alphabet from a string or
    list. If alphabet is None, then use the set of symbols of word as the
    alphabet.

    NOTE:
       Words is another way to construct words, and is much more versatile,
       taking various forms of data as input.

    EXAMPLES:
        sage: u = Word("abbabaab"); u
        word: abbabaab
        sage: u.alphabet()
        {'a', 'b'}

        sage: w = Word("abbabaab", alphabet="abc"); w
        word: abbabaab
        sage: w.alphabet()
        {'a', 'b', 'c'}

        sage: Word(["a", "b", "b", "a", "b", "a", "a", "b"])
        word: abbabaab

        sage: Word([0,1,1,0,1,0])
        word: 011010
        
        sage: Word()
        word:

        sage: f = lambda n : 1
        sage: Word(f)
        Traceback (most recent call last):
          ...
        TypeError: must supply an alphabet for words not defined by lists of strings
        sage: Word(f, alphabet=[1])
        Infinite word over {1}
    """
    if word is None and alphabet is None:
        return Words("")(word)
    if not isinstance(word, (str,list)):
        if alphabet is None:
            raise TypeError, "must supply an alphabet for words not defined by lists of strings"
        return Words(alphabet)(word)
    if word is None:
        if alphabet is None:
            alphabet = ""
    else:
        if alphabet is None:
            alphabet = set(word)
    return Words(alphabet)(word)

class Words(SageObject):
    r"""
    Defines the set of words over an alphabet.
    
    INPUT:
        alpha -- either an instance of Alphabet or an argument suitable to build one.
    
    OUTPUT:
        words -- the set object

    EXAMPLES:
    You build a set like this:
        sage: W = Words('ab'); W
        Words over {'a', 'b'}
        
    We can now ask our set what is its alphabet,
        sage: W().alphabet()
        {'a', 'b'}
        
    and build words from the set by calling the set with appropriate arguments
        sage: W('abba')
        word: abba
    
    If we try using unknown symbols, the word will be rejected
        sage: W('abc')
        Traceback (most recent call last):
          ...
        IndexError: symbol not in alphabet: 'c'
    """
    def __new__(cls, alpha):
        r"""
        TESTS:
            sage: wab = Words('ab')
            sage: wab == loads(dumps(wab))
            True
            sage: wab is Words('ab')
            True
        """
        if not isinstance(alpha, Alphabet):
            try:
                alpha = Alphabet(alpha)
            except (TypeError, ValueError):
                raise TypeError, "alpha is not an alphabet and cannot be used to build one"
        if alpha not in cls._words_cache:
            res = super(Words, cls).__new__(cls)
            res._alpha = alpha
            cls._words_cache[alpha] = res
        return cls._words_cache[alpha]
    
    _words_cache = WeakValueDictionary()
    
    def __getnewargs__(self):
        r"""
        Support for pickle
        
        TESTS:
            sage: Words('abc').__getnewargs__()
            ({'a', 'b', 'c'},)
        """
        return (self._alpha,)
    
    def __getstate__(self):
        r"""
        Support for pickle
        
        TESTS:
            sage: Words('abc').__getstate__()
        """
        pass
        
    def __setstate__(self):
        r"""
        Support for pickle
        
        TESTS:
            sage: Words('abc').__setstate__()
        """
        pass
    
    def alphabet(self):
        r"""
        This function returns the alphabet over which the set is defined.
        
        EXAMPLES:
            sage: Words('abc').alphabet()
            {'a', 'b', 'c'}
        """
        return self._alpha
        
    def dimension(self):
        r"""
        Return the size of the alphabet.
        
        EXAMPLES:
            sage: Words('abcdef').dimension()
            6
            sage: Words('').dimension()
            0
        """
        return len(self.alphabet())
    
    def __call__(self, obj=None, part=slice(None), format=None):
        r"""
        TESTS:
            sage: from itertools import repeat, count, imap
            sage: W = Words('ab')
            sage: W(format='empty')
            word: 
            sage: W(['a', 'b'], format='empty')
            Traceback (most recent call last):
              ...
            TypeError: trying to build an empty word with something other than None
            sage: W(['a', 'b', 'b'])
            word: abb
            sage: W(['a', 'b', 'b'], format='list')
            word: abb
            sage: W(10, format='list')
            Traceback (most recent call last):
              ...
            TypeError: trying to build a word backed by a list with a sequence not providing the required operations
            sage: Words([0, 1])(lambda x: x%2)
            Infinite word over {0, 1}
            sage: W = Words([0, 1, 2])
            sage: W(lambda x: x%3, slice(0,10))
            word: 0120120120
            sage: W(repeat(1))
            Infinite word over {0, 1, 2}
            sage: Words(xrange(10))(imap(str, count()), slice(10))
            word: 0123456789
            sage: Words(xrange(10))(count(), slice(10, 0, -2))
            word: 97531
        """
        if not slice_ok(part):
            raise TypeError, "part is not a slice or has wrong types for elements"
        
        if format is None:
            if is_Word(obj) and obj.parent() == self:
                return obj
            elif obj is None:
                format = 'empty'
            elif is_iterable(obj):
                if haslen(obj):
                    format = 'list'
                else:
                    format = 'iterator'
            elif callable(obj):
                format = 'function'
            else:
                pass # Don't set format if we don't know
                
        if format == 'empty':
            if obj is not None:
                raise TypeError, "trying to build an empty word with something other than None"
            return FiniteWord_list((), self)
        elif format == 'list':
            if not (is_iterable(obj) and haslen(obj)):
                raise TypeError, "trying to build a word backed by a list with a sequence not providing the required operations"
            return FiniteWord_list(obj, self)[part]
        elif format == 'function':
            if not callable(obj):
                raise TypeError, "trying to build a word backed by a function with a non-callable"
            return InfiniteWord_func(obj, self)[part]
        elif format == 'iterator':
            if not is_iterable(obj):
                raise TypeError, "trying to build a word backed by an iterator with a non-iterable"
            return InfiniteWord_iter(obj, self)[part]
        raise NotImplementedError
        
    def __contains__(self, w):
        r"""
        Returns whether w is included in this set or not.
        
        INPUT:
            w -- a word
            
        OUTPUT:
            boolean -- is w in the set
            
        EXAMPLES:
            sage: Wab = Words('ab')
            sage: Wabc = Words('abc')
            sage: abba = Wab('abba')
            sage: abc = Wabc('abc')
            sage: abba in Wab
            True
            sage: abba in Wabc
            True
            sage: abc in Wabc
            True
            sage: abc in Wab
            False
            sage: Wabc('baab') in Wab # todo: not implemented
            True
        """
        if not is_Word(w):
            return False
        if w._parent == self:
            return True
        else:
            return w._parent.alphabet() <= self.alphabet()
        
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: Words('ab')._repr_()
            "Words over {'a', 'b'}"
        """
        return "Words over %r" % self._alpha
    
    def _latex_(self):
        r"""
        Returns a latex representation of the object
        
        TESTS:
            sage: Words('ab')._latex_()
            '\\{\\text{a}, \\text{b}\\}^*'
        """
        return latex(self._alpha) + "^*"

def is_Word(obj):
    r"""
    Returns true if obj is a word.
    
    EXAMPLES:
        sage: is_Word(33)
        False
        sage: is_Word(Word('abba'))
        True
    """
    return isinstance(obj, GenericWord)

def is_FiniteWord(obj):
    r"""
    Returns true if obj is a finite word.
    
    EXAMPLES:
        sage: is_FiniteWord(33)
        False
        sage: is_FiniteWord(Word('baab'))
        True
    """
    return isinstance(obj, FiniteWord)

class GenericWord(SageObject):
    def __init__(self, parent):
        r"""
        Initialize the GenericWord object with the parent relationship.
        
        TESTS:
            sage: g = sage.words.word.GenericWord(Words('abc'))
            sage: g = sage.words.word.GenericWord(33)
            Traceback (most recent call last):
            ...
            TypeError: the parent must be an instance of Words
            sage: loads(dumps(g))
            Word
        """
        if not isinstance(parent, Words):
            raise TypeError, "the parent must be an instance of Words"
        self._parent = parent
    
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: sage.words.word.GenericWord(Words('ab'))._repr_()
            'Word'
        """
        return "Word"
    
    def __iter__(self):
        r"""
        Returns an iterator over the symbols of the word
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: w = W('abba')
            sage: list(w)           # indirect test
            ['a', 'b', 'b', 'a']
        """
        return self._iter_syms()
    
    def parent(self):
        r"""
        Returns the parent object from which the word was created.
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: w = W('abba')
            sage: w.parent()
            Words over {'a', 'b'}
            sage: w.parent() is W
            True
        """
        return self._parent
    
    def alphabet(self):
        r"""
        Returns the alphabet of the parent.
        
        EXAMPLES:
            sage: Words('abc')('abbacbaab').alphabet()
            {'a', 'b', 'c'}
        """
        return self._parent.alphabet()
    
    def coerce(self, other):
        r"""
        Returns a pair of words in a common set or raises an exception
        
        This function begins by checking if both words have the same parent.
        If this is the case, then no work is done and both words are returned
        as-is.
        
        Otherwise it will attempt to convert other to the domain of self.
        If that fails, it will attempt to convert self to the domain of 
        other.  If both attempts fail, it raises a TypeError to signal 
        failure.
        
        EXAMPLES:
            sage: W1 = Words('abc'); W2 = Words('ab')
            sage: w1 = W1('abc'); w2 = W2('abba'); w3 = W1('baab')
            sage: w1.parent() is w2.parent()
            False
            sage: a, b = w1.coerce(w2)
            sage: a.parent() is b.parent()
            True
        """
        if self._parent != other._parent:
            try:
                other = self.parent()(other)
            except:
                try:
                    self = other.parent()(self)
                except:
                    raise TypeError, "no coercion rule between %r and %r" % (self.alphabet(), other.alphabet())
        return self, other
    
    # Implementations should only implement one of these functions
    # but they MUST implement at least one of them.  Otherwise, iteration
    # is broken on these implementations (and it is used a lot).
    def _iter_vals(self):
        r"""
        Returns an iterator over the internal values of the word
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: w = W('abba')
            sage: list(w._iter_vals())
            [0, 1, 1, 0]
        """
        fn = self.alphabet().to_int
        for s in self._iter_syms():
            yield fn(s)
    
    def _iter_syms(self):
        r"""
        Returns an iterator over the symbols of the word
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: w = W('abba')
            sage: list(w._iter_syms())
            ['a', 'b', 'b', 'a']
        """
        fn = self.alphabet().to_sym
        for i in self._iter_vals():
            yield fn(i)
    
    def _check_getitem_args(self, key):
        """
        TESTS:
            sage: from sage.words.word import GenericWord
            sage: w = Words('')()
            sage: GenericWord._check_getitem_args(w, 1)
            1
            sage: GenericWord._check_getitem_args(w, "abc")
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            sage: GenericWord._check_getitem_args(w, slice(1, 2, 3))
            slice(1, 2, 3)
            sage: GenericWord._check_getitem_args(w, slice("a"))
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            sage: GenericWord._check_getitem_args(w, slice("a", 1))
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            sage: GenericWord._check_getitem_args(w, slice(1, 1, "a"))
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
        """
        if slice_ok(key):
            start, stop, step = key.start, key.stop, key.step
            if step is None:
                step = 1
            if key.step == 0:
                raise ValueError, "slice step cannot be zero"
            return slice(start, stop, step)
        elif isint(key):
            return int(key)
        else:
            raise TypeError, "word indices must be integers"

#######################################################################
#                                                                     #
#                           Finite words                              #
#                                                                     #
#######################################################################

class FiniteWord(GenericWord):
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: Word('abc')._repr_()
            'word: abc'
            sage: Word([0, 1, 0, 1, 1] * 10)._repr_()
            'Finite word of length 50 over {0, 1}'
        """
        if len(self) < 40:
            return str(self)
        else:
            return "Finite word of length %s over %r" % (len(self), self.alphabet())

    def __mul__(self, other):
        r"""
        Concatenates two words.
        
        EXAMPLES:
            sage: W = Words([0, 1])
            sage: W() * W(lambda x:x%2, slice(3))
            word: 010
            sage: Words([0, 1, 2])(lambda x:x%3, slice(3)) * Words('01234')('01234')
            Traceback (most recent call last):
            ...
            TypeError: no coercion rule between {0, 1, 2} and {'0', '1', '2', '3', '4'}
        """
        self, other = self.coerce(other)
        w = Word_conc(self, other)
        return self.parent()(Word_conc(self, other), slice(len(w)))
        
    def __pow__(self, exp):
        r"""
        Return the power $w^{exp}$. If $exp$ is $\infty$, returns the infinite
        periodic word of base self. Otherwise, $|w|\cdot exp$ must be 
        an non negative integer.
                
        EXAMPLES:

        You can take integer power :
            sage: W = Words(range(6)); w = W(range(6)); w
            word: 012345
            sage: w^2
            word: 012345012345
            sage: w^1
            word: 012345
            sage: w^0
            word: 
            sage: w^(-1)
            Traceback (most recent call last):
            ...
            ValueError: The exponent must be positive.

        You can take rational powers :
            sage: W = Words(range(6)); w = W(range(6)); w
            word: 012345
            sage: w^(.5)
            word: 012
            sage: w^(1/3)
            word: 01
            sage: (w*w)^(1/2) == w
            True
            sage: w^(5/2)
            word: 012345012345012
            
        ...but the length of the word times the exponent must be an integer :
            sage: W = Words(range(6)); w = W(range(6))
            sage: w^(1/4)
            Traceback (most recent call last):
            ...
            ValueError: Power of the word is not defined on the exponent 1/4
            
        You can take infinite power :
            sage: W = Words(range(6)); w = W(range(6)); w
            word: 012345
            sage: w^oo
            Infinite word over {0, 1, 2, 3, 4, 5}
            sage: (w^oo)[10000000:20000000]                         
            Finite word of length 10000000 over {0, 1, 2, 3, 4, 5}
            sage: (w^oo)[10000000:10000020]
            word: 45012345012345012345
            sage: W()^oo
            word: 
        """
        if exp is infinity:
            if self.is_empty():
                return self
            else:
                return self.parent()(lambda n: self[n % len(self)])
        
        nbCaracteres = len(self)*exp
        
        #If exp*|self| is not an integer
        if int(nbCaracteres) != nbCaracteres :
            raise ValueError, "Power of the word is not defined on the exponent %s"%exp

        #If exp is negative
        elif exp < 0 :
            raise ValueError, "The exponent must be positive."
        
        #If exp is not an integer
        elif int(exp) != exp :
            return ( self ** int(exp) ) * self[:int(nbCaracteres)%len(self)]
            
        #Base of induction
        elif exp == 0:
            return self.parent()()
        elif exp == 1:
            return self
        else :
            nexp = int(exp / 2)
            over = exp % 2
            res = (self * self) ** nexp
            if over == 1:
                res *= self
            return res
    
    def __str__(self):
        r"""
        Returns the full string representation of the word.
        
        TESTS:
            sage: Word('abc').__str__()
            'word: abc'
            sage: Words([0, 1])([0, 1, 0, 0, 1] * 10).__str__()
            'word: 01001010010100101001010010100101001010010100101001'
        """
        return 'word: ' + self.string_rep()
    
    def string_rep(self):
        r"""
        Returns the raw sequence of symbols as a string.
        
        EXAMPLES:
            sage: Words('ab')('abbabaab').string_rep()
            'abbabaab'
            sage: Words(range(2))([0, 1, 0, 0, 1]).string_rep()
            '01001'
        """
        return ''.join(map(str, self))
    
    def __cmp__(self, other):
        """
        Compares two words lexicographically.  Provides for all normal comparison operators.
        
        EXAMPLES:
            sage: W1 = Words('12'); W2 = Words('123')
            sage: W2('123').__cmp__(W1('1211')) > 0
            True
            sage: W1('2111').__cmp__(W2('12')) > 0
            True
            sage: W2('123').__cmp__(W2('123')) == 0
            True
            sage: W1('121').__cmp__(W2('121')) == 0
            True
            sage: W2('123').__cmp__(W1('22')) < 0
            True
            sage: W1('122').__cmp__(W2('32')) < 0
            True
            sage: W1('122').__cmp__(Words('ab')('abba'))  # todo: not implemented
            Traceback (most recent call last):
            ...
            TypeError: no coercion rule between {'1', '2'} and {'a', 'b'}
        """
        if not is_Word(other):
            return NotImplemented
        try:
            self, other = self.coerce(other)
        except TypeError:
            return NotImplemented
        for (c1, c2) in izip(self._iter_vals(), other._iter_vals()):
            r = c1 - c2
            if r != 0: return r
        return len(self) - len(other)
    
    def __hash__(self):
        r"""
        Returns the hash for this word.
        
        TESTS:
             sage: h = hash(Word('abc'))    # indirect test
             sage: Word('abc').__hash__() == Word('abc').__hash__()
             True
        """
        res = 5381
        for s in self._iter_vals():
            res = ((res << 5) + res) + s
        return res
        
    def is_empty(self):
        """
        Return True if the length of the receiver is zero and False otherwise.
        
        EXAMPLES:
            sage: W=Words('ab')
            sage: W().is_empty()
            True
            sage: W('a').is_empty()
            False
        """
        return len(self)==0
    
    def is_prefix_of(self, other):
        """
        w.is_prefix_of(other) -> True or False
        
        Return True if w is prefix of other.
        
        EXAMPLES:
            sage: V = Words('0123456789')
            sage: w = V('0123456789')
            sage: y = V('012345')
            sage: y.is_prefix_of(w)
            True
            sage: w.is_prefix_of(y) 
            False
            sage: W = Words('ab')
            sage: w.is_prefix_of(W())
            False
            sage: W().is_prefix_of(w)
            True
            sage: W().is_prefix_of(W())
            True
        """
        return self == other[:len(self)]
    
    def is_proper_prefix_of(self, other):
        """
        Returns true if the reciever is a proper prefix of other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12').is_proper_prefix_of(W('123'))
            True
            sage: W('12').is_proper_prefix_of(W('12'))
            False
            sage: W().is_proper_prefix_of(W('123'))
            True
            sage: W('123').is_proper_prefix_of(W('12'))
            False
            sage: W().is_proper_prefix_of(W())
            False
        """
        return self.is_prefix_of(other) and len(self) < len(other)
    
    def is_suffix_of(self, other):
        """
        w.is_suffix_of(other) -> True or False
        
        Return True if w is suffix of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: w = W('0123456789')
            sage: y = W('56789')
            sage: y.is_suffix_of(w)
            True
            sage: w.is_suffix_of(y)
            False
            sage: W('579').is_suffix_of(w)
            False
            sage: W().is_suffix_of(y)
            True
            sage: w.is_suffix_of(W())    
            False
            sage: W().is_suffix_of(W())
            True
        """
        return self.is_empty() or self == other[-len(self):]
    
    def is_proper_suffix_of(self, other):
        """
        Returns true of the reciever is a proper suffix of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('23').is_proper_suffix_of(W('123'))
            True
            sage: W('12').is_proper_suffix_of(W('12'))
            False
            sage: W().is_proper_suffix_of(W('123'))
            True
            sage: W('123').is_proper_suffix_of(W('12'))
            False
        """
        return self.is_suffix_of(other) and len(self) < len(other)
    
    def reversal(self):
        """
        w.reversal() -> FiniteWord
        
        return the reversal of the receiver
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('124563').reversal()
            word: 365421
        """
        return self[::-1]
    
    def is_palindrome(self):
        """
        w.is_palindrome() -> True or False
        
        return True if the receiver is a palindrome
        
        EXAMPLES :
            sage: W=Words('abcdefghijklmnopqrstuvwxyz I')
            sage: W('esope reste ici et se repose').is_palindrome()
            False
            sage: W('esoperesteicietserepose').is_palindrome()
            True
            sage: W('I saw I was I').is_palindrome()
            True
            
        TESTS:
            sage: Y=Words('ab')
            sage: Y().is_palindrome()
            True
            sage: Y('a').is_palindrome()
            True
            sage: Y('ab').is_palindrome()
            False
            sage: Y('aba').is_palindrome()
            True
            sage: Y('aa').is_palindrome() 
            True
        """
        l = len(self)
        return self[:l/2] == self[l/2 + l%2:].reversal()
    
    def lps(self):
        """
        Return the longest palindrome suffix of the receiver.
        
        EXAMPLES:
            sage: W=Words('0167ab')
            sage: W('0111').lps()
            word: 111
            sage: W('011101').lps()
            word: 101
            sage: W('6667').lps()
            word: 7
            sage: W('abbabaab').lps()
            word: baab
            sage: W().lps()
            word: 
        """
        for i in range(len(self)+1):
            fact = self[i:]
            if fact.is_palindrome():
                return fact
        
    def _lps(self, l=None):
        """
        Return the longest palindrome suffix of the receiver where 
        l ( = the length of the longest palindrome suffix of 
        the receiver[:-1] ) is known.
        
        For time complexity reason, we assume that the parameter 
        l given IS the length of the longest palindrome suffix of the receiver[:-1].
        No verification of that is made here.
        
        EXAMPLES :
            sage: W = Words('1234')
            sage: w = W('33412321')
            sage: w._lps(3)
            word: 12321
            sage: Y = Words('01')
            sage: w = Y('01101001')
            sage: w._lps(l=2)
            word: 1001
            sage: w._lps()          
            word: 1001
            sage: w._lps(None)
            word: 1001
            sage: w._lps(4) #No verification of the given length of the precedent lps
            word: 101001
            sage: Y()._lps(2)
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: v=Words('ab')('abbabaab')
            sage: pal=v[:0] 
            sage: for i in range(1,len(v)+1): 
            ...     pal=v[:i]._lps(len(pal))
            ...     print pal
            ...   
            word: a
            word: b
            word: bb
            word: abba
            word: bab
            word: aba
            word: aa
            word: baab
        """
        if l == None:
            return self.lps()
                    
        #If l == len(w[:-1]), there is no shortcut
        if len(self) == l + 1:
            return self.lps()
        
        #Obtain the letter to the left (g) and to the right (d) of the 
        #precedent lps of self
        g = self[-l-2]
        d = self[-1]
        
        #If the word g*d is a palindrome, the result follows
        if self.parent()([g, d]).is_palindrome():
            return self[-l-2:]
        
        #Otherwise, the length of the lps of self is smallest than l+2
        else:
            return self[-l-1:].lps()
                
    def palindromes(self):
        r"""
        Returns the set of all palindromic factors of the receiver.
        
        EXAMPLES:
            sage: W = Words('01')
            sage: W('01101001').palindromes() == set([W(), W('1'), W('101'), W('0110'), W('11'), W('00'), W('1001'), W('010'), W('0')])
            True
            sage: W('00000').palindromes() == set([W('000'), W('0000'), W('0'), W('00'), W('00000'), W()])
            True
            sage: W('0').palindromes() == set([W(), W('0')])
            True
            sage: W('').palindromes() == set([W()])
            True
            sage: W().palindromes() == set([W()])
            True
        """
        #TODO : (Seb) Ajouter la reference pertinente de cet algo...
        #Initialize the answer
        set_pal=set()
        
        pal = self.parent()()
        set_pal.add(pal)
        
        #For all the non empty prefixes of the receiver,
        for i in xrange(1,len(self)+1):
            
            #compute its longest palindromic suffix using the precedent lps (pal)
            pal  = self[:i]._lps(len(pal))
            
            set_pal.add(pal)
            
        return set_pal
    
    def defect(self):
        """
        Return the defect of the receiver, i.e. D(w)=|w|+1-|Pal(w)|.

        [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the Palindromic Complexity
        of Infinite Words, in J. Berstel, J. Karhumaki, D. Perrin, Eds, Combinatorics
        on Words with Applications, International Journal of Foundation of Computer 
        Science, Vol. 15, No. 2 (2004) 293--306.
        
        EXAMPLES:
            sage: words.ThueMorseWord()[:100].defect()
            16
            sage: words.FibonacciWord()[:100].defect()
            0
            sage: W = Words('01')
            sage: W('000000000000').defect()
            0
            sage: W('011010011001').defect()
            2
            sage: W('0101001010001').defect()
            0
            sage: W().defect()
            0
        """
        return len(self)+1-len(self.palindromes())
    
    def is_full(self):
        """
        Return true if the receiver has defect 0.
        
        Definition. A word is full if its defect is zero (see [1]).

        [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the Palindromic Complexity
        of Infinite Words, in J. Berstel, J. Karhumaki, D. Perrin, Eds, Combinatorics
        on Words with Applications, International Journal of Foundation of Computer 
        Science, Vol. 15, No. 2 (2004) 293--306.
        
        EXAMPLES:
            sage: words.ThueMorseWord()[:100].is_full()
            False
            sage: words.FibonacciWord()[:100].is_full()
            True
            sage: Words('0')('000000000000000').is_full()
            True
            sage: Words('01')('011010011001').is_full()
            False
            sage: Words('123456789')('2194').is_full()
            True
            sage: Words('ab')().is_full()
            True
        """
        return self.defect() == 0
    
    def palindromic_closure(self, side='right'):
        """
        w.palindromic_closure() -> FiniteWord
        
        Retourne le plus petit palindrome ayant self comme prefixe.
        
        EXAMPLES:
            sage: W = Words('1234567890')
            sage: W('1233').palindromic_closure()
            word: 123321
            sage: W('12332').palindromic_closure()
            word: 123321
            sage: W('0110343').palindromic_closure()
            word: 01103430110
            sage: W('0110343').palindromic_closure(side='left')
            word: 3430110343
            sage: W('01105678').palindromic_closure(side='left')
            word: 876501105678
        """
        if side == 'right':
            l = len(self.lps())
            return self * self[-(l+1)::-1]
        elif side == 'left':
            l = len(self.reversal().lps())
            return self[:l-1:-1] * self
        else:
            raise ValueError, "side must be either 'left' or 'right' (not %s) " % side
    
    def iterated_palindromic_closure(self, side='right'):
        """
        Returns the iterated palindromic closure of the receiver.
        
        INPUT:
            side -- can be any of the following:
                          'right' or 'left' (default: 'right')
                    
        EXAMPLES:
            sage: W = Words('123')
            sage: W('123').iterated_palindromic_closure()
            word: 1213121
            sage: W('123').iterated_palindromic_closure(side='left')
            word: 3231323
            sage: W('1').iterated_palindromic_closure()
            word: 1
            sage: W().iterated_palindromic_closure()
            word: 
        """
        if side == 'right':
            par = self.parent()
            return reduce(lambda r, s: (r*par([s])).palindromic_closure(), 
                            self, par())
        elif side == 'left':
            return self.reversal().iterated_palindromic_closure()
        else:
            raise ValueError, "side must be either 'left' or 'right' (not %s) " % side
    
    def is_symmetric(self):
        """
        Returns true if the receiver is symmetric, i.e. the product 
        of two palindromes.

        REFERENCES :        
        [1] S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the Palindromic Complexity
        of Infinite Words, in J. Berstel, J. Karhumaki, D. Perrin, Eds, Combinatorics
        on Words with Applications, International Journal of Foundation of Computer 
        Science, Vol. 15, No. 2 (2004) 293--306.
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: W('abbabab').is_symmetric()
            True
            sage: W('ababa').is_symmetric()
            True
            sage: W('aababaabba').is_symmetric()
            False
        """
        for i in range(len(self)):
            if self[:i].is_palindrome() and self[i:].is_palindrome():
                return True
        return False
            
    
    def is_square(self):
        """
        Returns true if the receiver is a square.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('1212').is_square()
            True
            sage: W('1213').is_square()
            False
            sage: W('12123').is_square()
            False
            sage: W().is_square()
            True
        """
        if len(self) % 2 != 0:
            return False
        else:
            l = len(self) / 2
            return self[:l] == self[l:]
    
    def is_square_free(self):
        """
        Returns true if the receiver does not contain squares.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12312').is_square_free()
            True
            sage: W('31212').is_square_free()
            False
            sage: W().is_square_free()
            True
        """
        l = len(self)
        if l < 2:
            return True
        suff = self
        for i in xrange(0, l - 2):
            for ll in xrange(2, l-i+1, 2):
                if suff[:ll].is_square():
                    return False
            suff = suff[1:]
        return True
    
    def is_cube(self):
        """
        Returns true if the receiver is a cube.
        
        EXAMPLES:
            sage: W = Words('012')
            sage: W('012012012').is_cube()
            True
            sage: W('01010101').is_cube()
            False
            sage: W().is_cube()
            True
            sage: W('012012').is_cube()
            False
        """
        if len(self) % 3 != 0:
            return False
        l = len(self) / 3
        return self[:l] == self[l:2*l] == self[2*l:]
    
    def is_cube_free(self):
        """
        Returns true is the receiver does not contain cubes.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12312').is_cube_free()
            True
            sage: W('32221').is_cube_free()
            False
            sage: W().is_cube_free()
            True
        """
        l = len(self)
        if l < 3: 
            return True
        suff = self
        for i in xrange(0, l - 3):
            for ll in xrange(3, l-i+1, 3):
                if suff[:ll].is_cube():
                    return False
            suff = suff[1:]
        return True
    
        
    def is_quasiperiodic(self):
        """
        Returns true if the receiver is quasiperiodic.
        
        EXAMPLES:
            sage: W = Words('abc')
            sage: W('abaababaabaababaaba').is_quasiperiodic()
            True
            sage: W('abacaba').is_quasiperiodic()
            False
            sage: W('a').is_quasiperiodic()
            False
            sage: W().is_quasiperiodic()
            False
            sage: W('abaaba').is_quasiperiodic()
            True
        """
        l = len(self)
        
        if l <= 1:
           return False
              
        for i in range(1, l - 1):
            return_lengths = [len(x) for x in self.return_words(self[:i])]
            if return_lengths != []:
               if (max(return_lengths) <= i and self[l-i:l] == self[:i]):
                  return True
        return False    
   
        
    def quasiperiods(self):
        """
        Returns the quasiperiods of the receiver. 
        A finite or infinite word W is quasiperiodic if it can be constructed by 
        concatenations and superpositions of one of its proper factors u, 
        which is called a quasiperiod of W.     
    
        EXAMPLES:
            sage: W = Words('abc')
            sage: W('abaababaabaababaaba').quasiperiods()
            [word: aba, word: abaaba, word: abaababaaba]
            sage: W('abaaba').quasiperiods()
            [word: aba]
            sage: W('abacaba').quasiperiods()
            []
        """
        l = len(self)
        
        if l <= 1:
           return []
        
        Q = [] 
        for i in range(1, l - 1):
            return_lengths = [len(x) for x in self.return_words(self[:i])]
            if return_lengths != []:
               if (max(return_lengths) <= i and self[l-i:l] == self[:i]):
                  Q.append(self[:i])
        return Q            
    
    def commutes_with(self, other):
        """
        Returns true if the receiver commutes with other.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12').commutes_with(W('12'))
            True
            sage: W('12').commutes_with(W('11'))
            False
            sage: W().commutes_with(W('21'))
            True
        """
        return (self * other) == (other * self)
    
     
    def conjugate(self, pos):
        """
        Returns the conjugate at pos of the receiver.  pos can be any integer,
        the distance used is the modulo by the length of the receiver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12112').conjugate(1)
            word: 21121
            sage: W().conjugate(2)
            word: 
            sage: W('12112').conjugate(8)
            word: 12121
            sage: W('12112').conjugate(-1)
            word: 21211
        """
        if self.is_empty():
            return self
        pos_mod = pos % len(self)
        return self[pos_mod:] * self[:pos_mod]
        
    def _conjugates_list(self):
        r"""
        Returns the list of conjugates of the receiver, 
        ordered from the 0-th to the (L-1)-st conjugate,
        where L is the length of the receiver.
        
        TESTS:
            sage: W = Words('abc')
            sage: W('cbbca')._conjugates_list()
            [word: cbbca, word: bbcac, word: bcacb, word: cacbb, word: acbbc]
            sage: W('abcabc')._conjugates_list()
            [word: abcabc,
             word: bcabca,
             word: cabcab,
             word: abcabc,
             word: bcabca,
             word: cabcab]
            sage: W()._conjugates_list()
            [word: ]
            sage: W('a')._conjugates_list()
            [word: a]
        """
        S = [self]
        for i in range(1,len(self)):
            S.append(self.conjugate(i))
        return S
        
    def conjugates(self):
        """
        Returns the set of conjugates of the receiver.
        
        TESTS:
            sage: W = Words('abc')
            sage: W('cbbca').conjugates() == set([W('cacbb'),W('bbcac'),W('acbbc'),W('cbbca'),W('bcacb')])
            True
            sage: W('abcabc').conjugates() == set([W('abcabc'),W('bcabca'),W('cabcab')])
            True
            sage: W().conjugates() == set([W()])
            True
            sage: W('a').conjugates() == set([W('a')])
            True
        """
        S = set([self])
        for i in range(1,self.primitive_length()):
            S.add(self.conjugate(i))
        return S
    
    def conjugate_position(self, other):
        """
        Returns the position where the reciever is conjugate with other.
        Returns None if there is no such position.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12113').conjugate_position(W('31211'))
            1
            sage: W('12131').conjugate_position(W('12113')) is None
            True
            sage: W().conjugate_position(W('123')) is None
            True
        """
        if len(self) != len(other):
            return None
        self, conj = self.coerce(other)
        if self == conj:
            return 0
        for l in xrange(1, len(conj) - 1):
            conj = conj.conjugate(1)
            if self == conj:
                return l
        return None
    
    def is_conjugate_with(self, other):
        """
        Returns true if the receiver is a conjugate of other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('11213').is_conjugate_with(W('31121'))
            True
            sage: W().is_conjugate_with(W('123'))
            False
            sage: W('112131').is_conjugate_with(W('11213'))
            False
            sage: W('12131').is_conjugate_with(W('11213'))
            True
        """
        return self.conjugate_position(other) is not None
    
    def is_cadence(self, seq):
        """
        Returns true if seq is a cadence of the receiver.
        
        A cadence is a increasing sequence of indexes that all map to the
        same symbol.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('121132123').is_cadence([0, 2, 6])
            True
            sage: W('121132123').is_cadence([0, 1, 2])
            False
            sage: W('121132123').is_cadence([])
            True
        """
        if len(seq) == 0:
            return True
        try:
            it = iter(self)
            s = islice(it, seq[0], None).next()
            for i in xrange(1, len(seq)):
                steps = seq[i] - seq[i-1]
                for n in xrange(steps-1): it.next()
                if it.next() != s:
                    return False
        except StopIteration:
            return False
        return True
    
    def longest_common_prefix(self, other):
        """
        Return the longest common prefix of the receiver and other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: w=W('12345')
            sage: y=W('1236777')
            sage: w.longest_common_prefix(y)
            word: 123
            sage: w.longest_common_prefix(w)
            word: 12345
            sage: y.longest_common_prefix(w)
            word: 123
            sage: y.longest_common_prefix(w)==w.longest_common_prefix(y)
            True
            sage: y.longest_common_prefix(y)==y
            True
            sage: W().longest_common_prefix(w)
            word: 
            sage: w.longest_common_prefix(W()) == w
            False
            sage: w.longest_common_prefix(W()) == W()
            True
            sage: w.longest_common_prefix(w[:3]) == w[:3]
            True
            sage: w.longest_common_prefix(w[:3]) == w
            False
            sage: Words('12')("11").longest_common_prefix(Words('1')("1"))
            word: 1
        """
        self, other = self.coerce(other)
        self_iter, other_iter = self._iter_vals(), other._iter_vals()
        i = 0
        try:
            while True:
                if self_iter.next() != other_iter.next():
                    return self[:i]
                i += 1
        except StopIteration:  # one iterator finished
            if len(self) < len(other):
                return self
            else:
                return other
    
    def longest_common_suffix(self, other):
        """
        Return the longest common suffix of the receiver and other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: y = W('549332345')
            sage: w = W('203945')
            sage: w.longest_common_suffix(y)
            word: 45
            sage: w.longest_common_suffix(y.reversal())
            word: 3945
            sage: w.longest_common_suffix(W())
            word: 
            sage: W().longest_common_suffix(w)
            word: 
            sage: W().longest_common_suffix(W())
            word: 
            sage: w.longest_common_suffix(w[3:]) == w[3:]
            True
            sage: w.longest_common_suffix(w[3:]) == w
            False
        """
        self, other = self.coerce(other)
        i = 0
        while(i < min(len(self), len(other)) and self._get_val(-(i+1)) == other._get_val(-(i+1))):
            i += 1
        if i == 0:
            return self.parent()()
        return self[-i:]
    
    def prefix_function_table(self):
        """
        Returns a vector containing the length of the proper prefix-suffixes
        for all the non empty prefixes of the receiver.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121321').prefix_function_table()
            [0, 0, 1, 0, 0, 1]
            sage: W('1241245').prefix_function_table()
            [0, 0, 0, 1, 2, 3, 0]
            sage: W().prefix_function_table()
            []
        """
        k = 0
        res = list(repeat(0, len(self)))
        for q in xrange(1, len(self)):
            while k > 0 and self._get_val(k) != self._get_val(q):
                k = res[k-1]
            if self._get_val(k) == self._get_val(q):
                k += 1
            res[q] = k
        return res
    
    def length_max_prefix_suffix(self):
        """
        Returns the length of the longest proper prefix-suffix of the receiver.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121').length_max_prefix_suffix()
            1
            sage: W('1').length_max_prefix_suffix()
            0
            sage: W('1212').length_max_prefix_suffix()
            2
            sage: W('111').length_max_prefix_suffix()
            2
            sage: W().length_max_prefix_suffix() is None
            True
        """
        if len(self) == 0:
            return None
        return self.prefix_function_table()[-1]
    
    def longest_prefix_suffix(self):
        """
        Returns the longest proper prefix-suffix of the receiver
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121212').longest_prefix_suffix()
            word: 1212
            sage: W('12321').longest_prefix_suffix()
            word: 1
            sage: W().longest_prefix_suffix() is None
            True
        """
        if len(self) == 0:
            return None
        return self[:self.length_max_prefix_suffix()]
    
    def is_overlap(self):
        """
        Returns true if the receiver is an overlap.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('12121').is_overlap()
            True
            sage: W('123').is_overlap()
            False
            sage: W('1231').is_overlap()
            False
            sage: W('123123').is_overlap()
            False
            sage: W('1231231').is_overlap()
            True
            sage: W().is_overlap()
            False
        """
        if len(self) == 0:
            return False
        return self.length_max_prefix_suffix() > len(self)/2
    
    def primitive_length(self):
        """
        Returns the length of the primitive of the word.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('1231').primitive_length()
            4
            sage: W('121212').primitive_length()
            2
        """
        l = lu = len(self)
        if l == 0:
            return 0
        p = self.prefix_function_table()
        while l > 0:
            l = p[l-1]
            if lu % (lu - l) == 0:
                return lu - l
    
    def is_primitive(self):
        """
        Returns true if the receiver is primitive.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('1231').is_primitive()
            True
            sage: W('111').is_primitive()
            False
        """
        return len(self) == self.primitive_length()
    
    def primitive(self):
        """
        Returns the primitive of the word.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('12312').primitive()
            word: 12312
            sage: W('121212').primitive()
            word: 12
        """
        return self[:self.primitive_length()]
    
    def exponent(self):
        """
        Returns the exponent of the receiver.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('1231').exponent()
            1
            sage: W('121212').exponent()
            3
            sage: W().exponent()
            0
        """
        if len(self) == 0:
            return 0
        return len(self) / self.primitive_length()
        
    def overlap_partition(self, other, delay, p=None):
        """
        Return the equivalence class of the alphabet in order that the receiver
        overlaps other with the delay given.
        
        Creation des classes d'equivalence (partition) des lettres pour que
        le chevauchement donne par le decalage ait lieu.

        EXEMPLE :        
        decalage = +3
        cheval
           abcdef

        EXAMPLES:
            sage: W = Words('chevalbdf')
            sage: cheval = W('cheval')
            sage: abcdef = W('abcdef')
            sage: cheval.overlap_partition(abcdef,3)
            {{'c', 'l'}, {'d'}, {'e'}, {'f'}, {'h'}, {'v', 'a', 'b'}}
            sage: W = Words('abcdef')
            sage: w = W('abc')
            sage: y = W('def')
            sage: w.overlap_partition(y, -3)
            {{'a'}, {'b'}, {'c'}, {'d'}, {'e'}, {'f'}}
            sage: w.overlap_partition(y, -2)
            {{'a', 'f'}, {'b'}, {'c'}, {'d'}, {'e'}}
            sage: w.overlap_partition(y, -1)
            {{'a', 'e'}, {'b', 'f'}, {'c'}, {'d'}}
            sage: w.overlap_partition(y, 0)
            {{'a', 'd'}, {'b', 'e'}, {'c', 'f'}}
            sage: w.overlap_partition(y, 1)
            {{'a'}, {'b', 'd'}, {'c', 'e'}, {'f'}}
            sage: w.overlap_partition(y, 2)
            {{'a'}, {'b'}, {'c', 'd'}, {'e'}, {'f'}}
            sage: w.overlap_partition(y, 3)
            {{'a'}, {'b'}, {'c'}, {'d'}, {'e'}, {'f'}}
            sage: w.overlap_partition(y, 4)
            {{'a'}, {'b'}, {'c'}, {'d'}, {'e'}, {'f'}}
            sage: W = Words(range(2))
            sage: w = W([0,1,0,1,0,1]); w
            word: 010101
            sage: w.overlap_partition(w, 0)
            {{0}, {1}}
            sage: w.overlap_partition(w, 1)
            {{0, 1}}
        """
        if delay < 0:
            return other.overlap_partition(self, -delay, p)
        
        self, other = self.coerce(other)
        
        #Creation of the default evolving partition
        if p == None:
            p = DisjointSet(self.alphabet(), self.parent().alphabet().to_int)
        
        #Join the classes of each pair of letters that are one above the other
        for i in range(delay, min(len(other)+delay, len(self))):
            p.join(self[i], other[i-delay])
            
        return p
        
    def relabeling(self, partition):
        """
        Return the word obtain by relabelling each letter by its
        representant in the partition. The letter is not replaced if it is
        not in the partition.
        
        Retourne le mot obtenu en remplacant chaque caractere
        de w par son representant dans la partition ou par lui-meme
        s'il n'est pas dans la partition.
        
        EXAMPLE:
        cheval
           abcdef
          lave
        
        EXAMPLES:
            sage: W = Words('chevalbdf')
            sage: cheval = W('cheval')                
            sage: abcdef = W('abcdef')
            sage: p = cheval.overlap_partition(abcdef, 3); p
            {{'c', 'l'}, {'d'}, {'e'}, {'f'}, {'h'}, {'v', 'a', 'b'}}
            sage: set(p.representants()) == set(['c', 'e', 'd', 'f', 'h', 'v'])
            True
            sage: cheval.relabeling(p)
            word: chevvc
            sage: lave = W('lave')
            sage: lave.overlap_partition(abcdef, 1, p)
            {{'c', 'e', 'l'}, {'d'}, {'f'}, {'h'}, {'v', 'a', 'b'}}
            sage: cheval.relabeling(p)
            word: chcvvc
        """
        #TODO Si une lettre du receveur n'est pas dans la partition, 
        #     prefere-t-on retourner une erreur?
        #TODO On pourrait surrement retourner un word_iterateur ou fn si
        #     self est de ce type.
        W = Words(partition.representants())
        w = []
        for c in self:
            rep_c = partition.representant_of(c)
            if rep_c is None:
                w.append(c)
            else:
                w.append(rep_c)
        return W(w)
    
    def last_position_table(self):
        """
        Returns a table (of size 256) that contains the last position of 
        each symbol in the receiver. The symbols not present in the word 
        will have a position of None
        
        EXAMPLES:
            sage: Words('01234')('1231232').last_position_table()
            [-1, 3, 6, 5, -1]
        """
        res = [-1]*len(self.alphabet())
        for (i, s) in izip(count(), self._iter_vals()):
            res[s] = i
        return res
    
    def good_suffix_table(self):
        """
        Returns a table of the maximum skip you can do in order not to miss
        a possible occurrence of the receiver in a word
        
        This is a part of the boyer-moore algorithm to find factors.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('121321').good_suffix_table()
            [5, 5, 5, 5, 3, 3, 1]
            sage: W('12412').good_suffix_table()
            [3, 3, 3, 3, 3, 1]
        """
        l = len(self)
        p = self.reversal().prefix_function_table()
        res = [l - p[-1]]*(l+1)
        for i in xrange(1, l+1):
            j = l - p[i - 1]
            if res[j] > (i - p[i-1]):
                res[j] = i - p[i-1]
        return res
    
    def _pos_in(self, other, p):
        r"""
        Returns the position of the first occurrence of the receiver 
        starting at position p in other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('12')._pos_in(W('131231'), 2)
            2
            sage: W('12')._pos_in(W('131231'), 3) is None
            True
            sage: W('32')._pos_in(W('131231'), 0) is None
            True
        """
        lf = len(self)
        lm = len(other)
        if lf == 0 or lm == 0:
            return None
        occ = self.last_position_table()
        suff = self.good_suffix_table()
        s = p
        while s <= lm - lf:
            for j in xrange(lf-1, -1, -1):
                if self._get_val(j) != other._get_val(s+j):
                    s += max(suff[j + 1], j - occ[other._get_val(s+j)])
                    break
            else:
                return s
        return None
    
    def first_pos_in(self, other):
        r"""
        Returns the position of the first occurrence of the receiver in other
        or None if the receiver is not a factor of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('12').first_pos_in(W('131231'))
            2
            sage: W('32').first_pos_in(W('131231')) is None
            True
        """
        self, other = self.coerce(other)
        return self._pos_in(other, 0)
        
    
    def is_factor_of(self, other):
        r"""
        Returns true if the reciever is a factor of other.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('2113').is_factor_of(W('123121332131233121132123'))
            True
            sage: W('321').is_factor_of(W('1231241231312312312'))
            False
        """
        return self.first_pos_in(other) is not None
    
    def factor_occurrences_in(self, other):
        r"""
        Returns an iterator over all occurences (including overlapping ones)
        of this word in other in their order of appearance.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: list(W('121').factor_occurrences_in(W('121213211213')))
            [0, 2, 8]
        """
        self, other = self.coerce(other)
        if len(self) == 0:
            raise NotImplementedError, "undefined value"
        p = self._pos_in(other, 0)
        while p is not None:
            yield p
            p = self._pos_in(other, p+1)
    
    def nb_factor_occurrences_in(self, other):
        r"""
        Returns the number of times the receiver appears as a factor
        in other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W().nb_factor_occurrences_in(W('123'))
            Traceback (most recent call last):
            ...
            NotImplementedError: undefined value
            sage: W('123').nb_factor_occurrences_in(W('112332312313112332121123'))
            4
            sage: W('321').nb_factor_occurrences_in(W('11233231231311233221123'))
            0
        """
        return len_it(self.factor_occurrences_in(other))
    
    def is_subword_of(self, other):
        """
        Returns true is the receiver is a subword of other.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W().is_subword_of(W('123'))
            True
            sage: W('123').is_subword_of(W('3211333213233321'))
            True
            sage: W('321').is_subword_of(W('11122212112122133111222332'))
            False
        """
        self, other = self.coerce(other)
        its = self._iter_vals()
        try:
            s = its.next()
            for e in other._iter_vals():
                if s == e:
                    s = its.next()
            else:
                return False
        except StopIteration:
            return True
    
    def nb_subword_occurrences_in(self, other):
        r"""
        Returns the number of times the receiver appears in other as a subword.
        
        EXAMPLES:
            sage: W = Words('1234')
            sage: W().nb_subword_occurrences_in(W('123'))
            Traceback (most recent call last):
              ...
            NotImplementedError: undefined value
            sage: W('123').nb_subword_occurrences_in(W('1133432311132311112'))
            11
            sage: W('4321').nb_subword_occurrences_in(W('1132231112233212342231112'))
            0
            sage: W('3').nb_subword_occurrences_in(W('122332112321213'))
            4
        """
        self, other = self.coerce(other)
        ls = len(self)
        if ls == 0:
            raise NotImplementedError, "undefined value"
        elif ls == 1:
            return self.nb_factor_occurrences_in(other)
        elif len(other) < ls:
            return 0
        symb = self[:1]
        suffword = other
        suffsm = self[1:]
        n = 0
        cpt = 0
        i = symb.first_pos_in(suffword)
        while i is not None:
            suffword = suffword[i+1:]
            m = suffsm.nb_subword_occurrences_in(suffword)
            if m == 0: break
            n += m
            i = symb.first_pos_in(suffword)
        return n
    
    def _return_words_list(self, fact):
        r"""
        Returns the return words as a list in the order they appear in the word.
        
        TESTS:
            sage: W = Words('abc')
            sage: W('baccabccbacbca')._return_words_list(W('b'))
            [word: bacca, word: bcc, word: bac]
        """
        self, fact = self.coerce(fact)
        i = fact.first_pos_in(self)
        if i is None:
            return []
        w = self[i+1:]
        j = fact.first_pos_in(w)
        res = []
        while j is not None:
            res.append(self[i:i+j+1])
            w = w[j+1:]
            i += j+1
            j = fact.first_pos_in(w)
        return res
    
    def return_words(self, fact):
        r"""
        Returns the set of return words.  This is the set of all factors starting
        by the given factor and ending just before the next occurrence
        of this factor.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('21331233213231').return_words(W('2')) == set([W('21331'), W('233'), W('213')])
            True
            sage: W().return_words(W('213')) == set()
            True
            sage: W('121212').return_words(W('1212')) == set([W('12')])
            True
        """
        return set(self._return_words_list(fact))
    
    def complete_return_words(self, fact):
        """
        Returns the set of return words.  This is the set of all factors starting
        by the given factor and ending just after the next occurrence
        of this factor.
        
        EXAMPLES:
            sage: W = Words('123')
            sage: W('21331233213231').complete_return_words(W('2')) == set([W('213312'), W('2332'), W('2132')])
            True
            sage: W('').complete_return_words(W('213')) == set()
            True
            sage: W('121212').complete_return_words(W('1212')) == set([W('121212')])
            True
        """
        i = fact.first_pos_in(self)
        if i is None:
            return set()
        w = self[i+1:]
        j = fact.first_pos_in(w)
        res = set()
        while j is not None:
            res.add(self[i:i+j+len(fact)+1])
            w = w[j+1:]
            i += j+1
            j = fact.first_pos_in(w)
        return res
    
    def return_words_derivate(self, fact, W=None):
        r"""
        Returns the word generated by mapping a symbol to each occurrence of 
        the return words for the given factor dropping any dangling prefix and 
        suffix.
        
        The optional set of words parameter must be over an alphabet that contains
        as much symbols as there are different return words in the receiver otherwise
        there will be some breakage in the function.  The default value for this 
        parameter always repects this property.  The symbols are attributed to the
        words in the order they are discovered.
        
        EXAMPLES:
            sage: Words('123')('12131221312313122').return_words_derivate(Words('1')('1'))
            word: 123242
        """
        self, fact = self.coerce(fact)
        idx = 0
        tab = {}
        ret = map(lambda w: tab.setdefault(w, len(tab)) + 1, self._return_words_list(fact))
        if W is None:
            W = Words(xrange(1, len(tab)+1)) 
        return W(ret)
    
    def delta(self):
        """
        Returns the delta equivalent of the receiver. This is the word 
        composed of the length of consecutive runs of the same symbol.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('22112122').delta()
            word: 22112
            sage: W('555008').delta()
            word: 321
            sage: W().delta()
            word: 
        """
        if len(self) == 0:
            return Words([])()
        ss = self[0]
        c = 0
        v = list()
        max_c = 0
        for s in self:
            if s == ss:
                c += 1
                if c > max_c:
                    max_c = c
            else:
                v.append(c)
                ss = s
                c = 1
        v.append(c)
        return Words(xrange(1, max_c+1))(v)
    
    def delta_inv(self, W=Words([1, 2]), s=None):
        """
        Returns the inverse of the delta operator applied to the receiver.
        
        The symbols in the returned word will start at the specified symbol
        or the first one if None is specified (the default). The default
        alphabet is \{1, 2\}
        
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([2, 2, 1, 1]).delta_inv()
            word: 112212
            sage: W([1, 1, 1, 1]).delta_inv(Words('123'))
            word: 1231
            sage: W([2, 2, 1, 1, 2]).delta_inv(s=2)
            word: 22112122
        """
        if not all(imap(isint, self.alphabet())):
            raise ValueError, "delta_inv() can only be applied to word composed of integer symbols"
        if len(self) == 0:
            return W()
        if not isinstance(W, Words):
            raise TypeError, "W must be an instance of Words"
        if s is None:
            s = W.alphabet().to_sym(0)
        if s not in W.alphabet():
            raise ValueError, "starting symbol not in alphabet"
        v = []
        
        p = W.alphabet().to_int(s)
        al = cycle(imap(W.alphabet().to_sym, chain(xrange(p, len(W.alphabet())), xrange(p))))
        al.next()
        for e in self._iter_syms():
            v += ([s] * e)
            s = al.next()
        return W(v)
    
    def delta_derivate(self, W=None):
        """
        Returns the derivative under delta for the reciver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12211').delta_derivate()
            word: 22
            sage: W('1').delta_derivate(Words([1]))
            word: 1
            sage: W('2112').delta_derivate()
            word: 2
            sage: W('2211').delta_derivate()
            word: 22
            sage: W('112').delta_derivate()
            word: 2
            sage: W('11222').delta_derivate(Words([1, 2, 3]))
            word: 3
        """
        d = self.delta()
        if len(d) == 0:
            return d
        if W is None:
            W = d.parent()
        if d[0] != W.alphabet().max_sym():
            d = d[1:]
        if d[-1] != W.alphabet().max_sym():
            d = d[:-1]
        return d
    
    def delta_derivate_left(self, W=None):
        """
        Returns the derivative under delta for the reciver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12211').delta_derivate_left()
            word: 22
            sage: W('1').delta_derivate_left(Words([1]))
            word: 1
            sage: W('2112').delta_derivate_left()
            word: 21
            sage: W('2211').delta_derivate_left()
            word: 22
            sage: W('112').delta_derivate_left()
            word: 21
            sage: W('11222').delta_derivate_left(Words([1, 2, 3]))
            word: 3
        """
        d = self.delta()
        if len(d) == 0:
            return d
        if W is None:
            W = d.parent()
        if d[0] != W.alphabet().max_sym():
            d = d[1:]
        return d
    
    def delta_derivate_right(self, W=None):
        """
        Returns the right derivative under delta for the reciver.
        
        EXAMPLES:
            sage: W = Words('12')
            sage: W('12211').delta_derivate_right()
            word: 122
            sage: W('1').delta_derivate_right(Words([1]))
            word: 1
            sage: W('2112').delta_derivate_right()
            word: 12
            sage: W('2211').delta_derivate_right()
            word: 22
            sage: W('112').delta_derivate_right()
            word: 2
            sage: W('11222').delta_derivate_right(Words([1, 2, 3]))
            word: 23
        """
        d = self.delta()
        if len(d) == 0:
            return d
        if W is None:
            W = d.parent()
        if d[-1] != W.alphabet().max_sym():
            d = d[:-1]
        return d
    
    def phi(self):
        r"""
        Applies the phi function to the receiver and returns the result.
        
        INPUT:
            self -- must be a word over integers
                    
        OUTPUT:
            word -- the result of the phi function
            
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2]).phi()
            word: 222222
            sage: W().phi()
            word: 
            sage: W([2, 1, 2, 2, 1, 2, 2, 1, 2, 1]).phi()
            word: 212113
        """
        if self.is_empty():
            return self
        m = self
        v = []
        s_max = 0
        while len(m) > 1:
            v.append(m[0])
            if m[0] > s_max:
                s_max = m[0]
            m = m.delta()
        v.append(m[0])
        if m[0] > s_max:
            s_max = m[0]
        return Words(xrange(1, s_max+1))(v)
        
    def phi_inv(self, W=None):
        r"""
        Applied the inverse of the phi function and returns the result.
        
        INPUT:
            self -- must be a word over the integers
            W -- the set of words of the result. must also be over the integers
        
        OUTPUT:
            word -- the inverse of the phi function
        
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([2, 2, 2, 2, 1, 2]).phi_inv()
            word: 22112122
            sage: W([2, 2, 2]).phi_inv(Words([2, 3]))
            word: 2233
        """
        if W is None:
            W = self.parent()
        if self.is_empty():
            return W()
        v = self.parent()((self[-1],))
        for i in xrange(len(self) - 2, -1, -1):
            v = v.delta_inv(W, self[i])
        return v
    
    def _phi_inv_tab(self, tab):
        r"""
        Specialized version of phi_inv() for long or incremental words.
        
        TESTS:
            sage: Words([1, 2])([1, 1, 2, 2])._phi_inv_tab([2])
            word: 12211
        """
        res = self.delta_inv(s=tab[0])
        res = res[1:]
        for i in xrange(1, len(tab)):
            res = res.delta_inv(s=tab[i])
        return res
    
    def is_smooth_prefix(self):
        r"""
        Returns whether the receiver is the prefix of a smooth word of not.
        
        INPUT:
            self -- must be a word over the integer to get somthing else than False
            
        OUTPUT:
            boolean -- whether the receiver is a smooth prefix or not
        
        EXAMPLES:
            sage: W = Words([1, 2])
            sage: W([1, 1, 2, 2, 1, 2, 1, 1]).is_smooth_prefix()
            True
            sage: W([1, 2, 1, 2, 1, 2]).is_smooth_prefix()
            False
        """
        m = self
        while len(m) > 1:
            m = m.delta_derivate_right()
            if m not in self.parent():
                return False
        return True
    
    def is_lyndon(self):
        """
        Returns true if the reciever is a lyndon word.
        
        EXAMPLES:
            sage: W = Words('0123456789')
            sage: W('123132133').is_lyndon()
            True
            sage: W().is_lyndon()
            True
            sage: W('122112').is_lyndon()
            False
        """
        if len(self) == 0:
            return True
        s = self._get_val(0)
        for (e, i) in izip(self[1:]._iter_vals(), count(1)):
            if s < e:
                continue
            if not self < self[i:]:
                return False
        return True
        
    def BWT(self):
        """
        Returns the Burrows-Wheeler Transform (BWT) of the receiver,
        which is obtained by first listing the conjugates of the
        receiver in lexicographic order and then concatenating the
        final letters of the conjugates in this order.
        
        REFERENCES:
        M. Burrows, D.J. Wheeler, "A block-sorting lossless data
        compression algorithm", HP Lab Technical Report, 1994, available
        at http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html
        
        EXAMPLES:
            sage: W = Words('abc')
            sage: W('abaccaaba').BWT()
            word: cbaabaaca
            sage: W('abaab').BWT()
            word: bbaaa
            sage: W('bbabbaca').BWT()
            word: cbbbbaaa
            sage: W('aabaab').BWT()
            word: bbaaaa
            sage: Word().BWT()
            word: 
            sage: W('a').BWT()
            word: a
        """
        if self.is_empty():
           return self
        conjugates = self._conjugates_list()
        conjugates.sort()
        return self.parent()([x[len(x)-1] for x in conjugates])
    
    def _Duval_algorithm(self):
        """
        TESTS:
            sage: Words('01')('010010010001000')._Duval_algorithm()
            (01.001.001.0001)
            sage: Words('123')('122113112212')._Duval_algorithm()
            (122.113.112212)
        """
        t = Factorization()
        cm = self
        c = iter(cm)
        cc = iter(cm)
        cc.next()
        i = 0
        d = 1
        j = k = 1
        l = len(cm)
        
        while k < l:
            c, c_s = peek_it(c)
            cc, cc_s = peek_it(cc)
            if c_s < cc_s:
                cc.next()
                k += 1
                j = k
                d = k - i
                c = iter(cm)
            elif c_s == cc_s:
                cc.next()
                k += 1
                if (k - j) == d:
                    j = k
                    c = iter(cm)
                else:
                    c.next()
            else:
                i += d
                while i <= j:
                    i += d
                    t.append(cm[:d])
                    cm = cm[d:]
                c = iter(cm)
                cc = iter(cm)
                cc.next()
                i = j
                j += 1
                k = j
                d = 1
        i += d
        while i <= j:
            i += d
            t.append(cm[:d])
            cm = cm[d:]
        return t
    
    def Duval_factorization(self):
        r"""
        Returns the Duval factorization of the word.
        
        FIXME: apparently this means nothing.  And this does not
               even return a proper factorization.  So maybe it
               should go.
        
        OUTPUT:
            list -- the list of factors obtained
            
        EXAMPLES:
            sage: Words('01')('010010010001000').Duval_factorization()
            (01.001.001.0001)
        """
        return self._Duval_algorithm()
    
    def Lyndon_factorization(self):
        r"""
        Returns the Lyndon factorization of the word.
        
        OUTPUT:
            list -- the list of factors obtained
        
        EXAMPLES:
            sage: Words('01')('010010010001000').Lyndon_factorization()
            (01.001.001.0001.0.0.0)
            sage: Words('ab')('abbababbaababba').Lyndon_factorization()
            (abb.ababb.aababb.a)
        """
        tab = self._Duval_algorithm()
        l = sum(imap(len, tab))
        if l < len(self):
            tab += self[l:]._Duval_algorithm()
        return tab
    
    def standard_factorization(self):
        r"""
        Returns the standard factorization of word.
        
        OUTPUT:
            list -- the list of factors
        
        EXAMPLES:
            sage: Words('01')('0010110011').standard_factorization()
            (001011.0011)
            sage: Words('123')('1223312').standard_factorization()
            (12233.12)
        """
        suff = self[1:]
        for l in xrange(1, len(self)):
            pref = self[:l]
            if pref.is_lyndon() and suff.is_lyndon():
                return Factorization([pref, suff])
            suff = suff[1:]
        return Factorization(self, self.parent()())
    
    def standard_factorization_of_Lyndon_factorization(self):
        r"""
        Returns the standard factorization of the Lyndon factorization of the word.
        
        OUTPUT:
            list of lists -- the factorization
        
        EXAMPLES:
            sage: Words('123')('1221131122').standard_factorization_of_Lyndon_factorization()
            [(12.2), (1.13), (1.122)]
        """
        return map(FiniteWord.standard_factorization, self.Lyndon_factorization())
    
    def crochemore_factorization(self):
        r"""
        Returns the Crochemore factorization of the word as an ordered list of
        factors.
        
        The Crochemore factorization of a word w is the unique factorization
        (x_1, x_2, ..., x_n) of w with each xi satisfying either:
        
        C1. x_i is a letter that does not appear in u = x_1...x_{i-1};
        C2. x_i is the longest prefix of v = x_i...x_n that also has an 
        occurrence beginning within u = x_1...x_{i-1}.
        
        This is not a very good implementation, and should be improved.
        
        EXAMPLES:
            sage: x = Words('ab')('abababb')
            sage: x.crochemore_factorization()
            (a.b.abab.b)
            sage: mul(x.crochemore_factorization()) == x
            True
            sage: y = Words('abc')('abaababacabba')
            sage: y.crochemore_factorization()
            (a.b.a.aba.ba.c.ab.ba)
            sage: mul(y.crochemore_factorization()) == y
            True
            sage: x = Words([0, 1])([0,1,0,1,0,1,1])
            sage: x.crochemore_factorization()
            (0.1.0101.1)
            sage: mul(x.crochemore_factorization()) == x
            True
        """
        c = Factorization([self[:1]])
        u = self[:sum(map(len,c))] # = x_1 ... x_{i-1}
        v = self[sum(map(len,c)):] # = x_i ... x_n
        while v:
            # C1. x_i is a letter that does not appear in u = x_1...x_{i-1}
            if v[0] not in u:
                c.append(v[:1])
            else:
            # C2. x_i is the longest prefix of v = x_i...x_n that also has an
            #     occurrence beginning within u = x_1...x_{i-1}.
                xi = v
                while True:
                    if xi.first_pos_in(self) < len(u):
                        c.append(xi)
                        break
                    else:
                        xi = xi[:-1]
            u = self[:sum(map(len,c))] # = x_1 ... x_{i-1}
            v = self[sum(map(len,c)):] # = x_i ... x_n
        return c
            
    def is_balanced(self, q=1):
        r"""
        Returns whether or not the receiver is q-balanced.
        
        INPUT:
            q -- integer (default 1), the balance level
        
        OUTPUT:
            boolean -- the result
            
        EXAMPLES:
            sage: Words('123')('1213121').is_balanced()
            True
            sage: Words('12')('1122').is_balanced()
            False
            sage: Words('123')('121333121').is_balanced()
            False
            sage: Words('123')('121333121').is_balanced(2)
            False
            sage: Words('123')('121333121').is_balanced(3)
            True
            sage: Words('12')('121122121').is_balanced()
            False
            sage: Words('12')('121122121').is_balanced(2)
            True
            sage: Words('12')('121122121').is_balanced(-1)
            Traceback (most recent call last):
            ...
            TypeError: the balance level must be a positive integer
            sage: Words('12')('121122121').is_balanced(0)
            Traceback (most recent call last):
            ...
            TypeError: the balance level must be a positive integer
            sage: Words('12')('121122121').is_balanced('a')
            Traceback (most recent call last):
            ...
            TypeError: the balance level must be a positive integer
        """
        if not isint(q) or q <= 0:
           raise TypeError, "the balance level must be a positive integer"
        from sage.words.dictionary import Dictionary
        d = Dictionary(self)
        for i in xrange(2, len(self)+1):
            tab = [None] * len(self.alphabet())
            for j in xrange(len(tab)):
                tab[j] = set()
            for fact in ifilter(lambda f: len(f) == i, d):
                for (n, sym) in izip(count(), self.alphabet()):
                    tab[n].add(self.parent()(sym).nb_factor_occurrences_in(fact))
            for t in tab:
                if len(t) > q+1:
                    return False
        return True
    
    def freq(self):
        r"""
        Returns a table of the frequencies of the symbols
        
        OUTPUT:
            dict -- symbols associated to their frequency
            
        EXAMPLES:
            sage: Words('123')('1213121').freq()    # keys appear in random order
            {'1': 4, '2': 2, '3': 1}
            
        TESTS:
            sage: f = Words('123')('1213121').freq()
            sage: f['1'] == 4
            True
            sage: f['2'] == 2
            True
            sage: f['3'] == 1
            True
        """
        res = dict()
        for sym in self.alphabet():
            res[sym] = 0
        for s in self:
            res[s] += 1
        return res
        
    def parikh_vector(self):
        """
        Returns the Parikh vector of the receiver,
        i.e., the vector containing the number of occurrences 
        of each letter, given in the order of the alphabet.
        
        EXAMPLES:
            sage: Word('aabaa').parikh_vector()
            [4, 1]
            sage: Word('aabaacaccab').parikh_vector()
            [6, 3, 2]
            sage: Words('abc')('aabaa').parikh_vector()
            [4, 1, 0]
            sage: Word().parikh_vector()
            [0]
            sage: Word('a').parikh_vector()
            [1]
            sage: Words('abc')('a').parikh_vector()
            [1, 0, 0]
            sage: Words('ab')().parikh_vector()
            [0, 0]
            sage: Words('abc')().parikh_vector()
            [0, 0, 0]
            sage: Words('abcd')().parikh_vector()
            [0, 0, 0, 0]
        """
        v= [self.count(x) for x in list(self.parent().alphabet())[:-1]]
        return v + [len(self) - sum(v)]
    
    def _check_getitem_args(self, key):
        """
        TESTS:
            sage: from sage.words.word import FiniteWord
            sage: w = Words('1')('1111')
            sage: FiniteWord._check_getitem_args(w, slice(None))
            slice(None, None, 1)
            sage: FiniteWord._check_getitem_args(w, 3)
            3
            sage: FiniteWord._check_getitem_args(w, 4)
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: FiniteWord._check_getitem_args(w, -4)
            0
            sage: FiniteWord._check_getitem_args(w, -5)
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        key = super(FiniteWord, self)._check_getitem_args(key)
        if isinstance(key, slice): return key
        if key < 0:
            key += len(self)
        if key < 0 or key >= len(self):
            raise IndexError, "word index out of range"
        return key
    
    def apply_morphism(self,morphism,operation='*'):
        """
        Returns the word obtained by applying the morphism to self.
        
        INPUT:
            morphism -- Can be one of the following:
                1. a dictionary with the letters of self as keys.
                2. an instance of the morphism class.
        
        EXAMPLES:
            sage: n0, n1 = matrix(2,[1,1,1,0])**2, matrix(2,[2,1,1,0])**2
            sage: n = {0:n0, 1:n1}
            sage: w = words.ChristoffelWord(3,5)
            sage: w.apply_morphism(n)
            [18045  7561]
            [11069  4638]
        """
        lettre = self[0]
        if not morphism.has_key(lettre):
            raise TypeError, "The morphism is not defined on %s" % lettre
        result = morphism[lettre]
        for lettre in self[1:]:
            if not morphism.has_key(lettre):
                raise TypeError, "The morphism is not defined on %s" % lettre
            if operation == '*':
                result *= morphism[lettre]
            elif operation == '+':
                result += morphism[lettre]
            else:
                raise NotImplementedError
        return result
    
    def count(self, letter):
        """
        Count the number of occurrences of letter in self.
        
        EXAMPLES:
            sage: Words('ab')('abbabaab').count('a')
            4
        """
        return self.parent()([letter]).nb_factor_occurrences_in(self)

    def suffix_trie(self):
        r"""
        Returns the suffix trie of self.

        The suffix trie of a finite word w is a data structure representing
        the factors of w. It is a tree whose edges are labelled with
        letters of w, and whose leafs correspond to suffixes of w.

        See sage.words.suffix_trees.SuffixTrie? for more information.

        EXAMPLES:
            sage: w = Words("cao")("cacao")
            sage: w.suffix_trie()
            Suffix Trie of the word: cacao

            sage: w = Words([0,1])([0,1,0,1,1])
            sage: w.suffix_trie()
            Suffix Trie of the word: 01011
        """
        from sage.words.suffix_trees import SuffixTrie
        return SuffixTrie(self)

    def implicit_suffix_tree(self):
        r"""
        Returns the implicit suffix tree of self.

        The suffix tree of a word w is a compactification of the suffix
        trie for w. The compactification removes all nodes that have
        exactly one incoming edge and exactly one outgoing edge. It
        consists of two components: a tree and a word. Thus, instead of
        labelling the edges by factors of w, we can labelled them by
        indices of the occurrence of the factors in w. 

        See sage.words.suffix_trees.ImplicitSuffixTree? for more information.

        EXAMPLES:
            sage: w = Words("cao")("cacao")
            sage: w.implicit_suffix_tree()
            Implicit Suffix Tree of the word: cacao
            
            sage: w = Words([0,1])([0,1,0,1,1])
            sage: w.implicit_suffix_tree()
            Implicit Suffix Tree of the word: 01011
        """
        from sage.words.suffix_trees import ImplicitSuffixTree
        return ImplicitSuffixTree(self)

    def suffix_tree(self):
        r"""
        Alias for implicit_suffix_tree().
        
        EXAMPLES:
            sage: Words('ab')('abbabaab').suffix_tree()
            Implicit Suffix Tree of the word: abbabaab
        """
        return self.implicit_suffix_tree()

class FiniteWord_list(FiniteWord):
    r"""
    TESTS:
        sage: Words('01234')('01234', format='list')
        word: 01234
        sage: Words('123')(['1', '2', '3'], format='list')
        word: 123
        sage: Words('23')(('2', '2', '3'), format='list')
        word: 223
        sage: w = Words('0123')('012131210', format='list')
        sage: w == loads(dumps(w))
        True
    """
    def __init__(self, l, parent, _trans=True):
        r"""
        TESTS:
            sage: w = sage.words.word.FiniteWord_list([0, 1, 0, 0, 1], Words([0, 1]))
        """
        super(FiniteWord_list, self).__init__(parent)
        if _trans:
            fn = parent.alphabet().to_int
            typecode = {1:'B', 2:'I', 4:'L'}[dropwhile(lambda x: x < len(parent.alphabet())/256, [1, 2, 4]).next()]
            self.__l = array(typecode, imap(fn, l))
        else:
            self.__l = l
    
    def _iter_vals(self):
        r"""
        TESTS:
            sage: list(Words('1234')('1234')._iter_vals())
            [0, 1, 2, 3]
        """
        return iter(self.__l)
    
    def __len__(self):
        r"""
        TESTS:
            sage: len(Words('0123')('0123'))
            4
        """
        return len(self.__l)
    
    def _get_val(self, i):
        r"""
        TESTS:
            sage: w = Words('ab')('abb')
            sage: w._get_val(0)
            0
            sage: w._get_val(2)
            1
        """
        i = self._check_getitem_args(i)
        return self.__l[i]
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: w = Words('012345')('012345')
            sage: w[:]
            word: 012345
            sage: w[0:]
            word: 012345
            sage: w[10:]
            word: 
            sage: w[-2:]
            word: 45
            sage: w[-10:]
            word: 012345
            sage: w[:0]
            word: 
            sage: w[:2]
            word: 01
            sage: w[:10]
            word: 012345
            sage: w[:-1]
            word: 01234
            sage: w[:-10]
            word: 
            sage: w[::2]
            word: 024
            sage: w[::-2]
            word: 531
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[0]
            '0'
            sage: w[5]
            '5'
            sage: w[6]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: w[-1]
            '5'
            sage: w[-6]
            '0'
            sage: w[-7]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            return FiniteWord_list(self.__l[key], self.parent(), _trans=False)
        else:
            return self.parent().alphabet().to_sym(self.__l[key])
    
    def __mul__(self, other):
        r"""
        TESTS:
            sage: w = Words('012357')('123')
            sage: l = Words('57')('557')
            sage: w * l
            word: 123557
            sage: w * Words('01')(lambda x:str(x%2), slice(10))
            word: 1230101010101
        """
        if isinstance(other, FiniteWord_list):
            self, other = self.coerce(other)
            return FiniteWord_list(self.__l + other.__l, self.parent(), _trans=False)
        else:
            return super(FiniteWord_list, self).__mul__(other)

class FiniteWord_func(FiniteWord):
    r"""
    TESTS:
        #sage: w = Words([0, 1])(lambda i: i%2, slice(10))
        #sage: w == loads(dumps(w))     # broken (can't pickle functions)
        #True
    """
    def __init__(self, func, parent, start, stop, step):
        r"""
        TESTS:
            sage: w = sage.words.word.FiniteWord_func(lambda i: i%2, Words([0, 1]), None, 10, None)
            sage: w = sage.words.word.FiniteWord_func(lambda i: i%2, Words([0, 1]), 0, 10, 1)
        """
        super(FiniteWord_func, self).__init__(parent)
        start = start or 0
        step = step or 1
        self.__func = lambda x: func(start + x*step)
        self.__l = int((stop - start)/step)
    
    def _iter_syms(self):
        r"""
        TESTS:
            sage: list(Words('012345')(str, slice(1, 5))._iter_syms())
            ['1', '2', '3', '4']
        """
        for i in xrange(self.__l):
            yield self.__func(i)
    
    def __len__(self):
        r"""
        TESTS:
            sage: len(Words(range(1, 5))(lambda x: x, slice(1, 5)))
            4
        """
        return self.__l
    
    def _get_val(self, i):
        r"""
        TESTS:
            sage: w = Words('ab')(lambda i: {False:'a', True:'b'}[i > 0], slice(3))
            sage: w._get_val(0)
            0
            sage: w._get_val(2)
            1
            sage: w._get_val(-1)
            1
        """
        i = self._check_getitem_args(i)
        return self.parent().alphabet().to_int(self.__func(i))
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: w = Words('012345')(str, slice(6))
            sage: w[:]
            word: 012345
            sage: w[0:]
            word: 012345
            sage: w[10:]
            word: 
            sage: w[-2:]
            word: 45
            sage: w[-10:]
            word: 012345
            sage: w[:0]
            word: 
            sage: w[:2]
            word: 01
            sage: w[:10]
            word: 012345
            sage: w[:-1]
            word: 01234
            sage: w[:-10]
            word: 
            sage: w[::2]
            word: 024
            sage: w[::-2]
            word: 531
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[0]
            '0'
            sage: w[5]
            '5'
            sage: w[6]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: w[-1]
            '5'
            sage: w[-6]
            '0'
            sage: w[-7]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            return FiniteWord_func(self.__func, self.parent(), *slice_indices(key, len(self)))
        else:
            return self.__func(key)

class FiniteWord_iter(FiniteWord):
    r"""
    TESTS:
        #sage: w = Words('ab')('abba', slice(4), format='iterator')
        #sage: w == loads(dumps(w))  # broken (islice does not pickle correctly)
        #True
    """
    def __init__(self, it, parent, start, stop, step):
        r"""
        TESTS:
            sage: w = sage.words.word.FiniteWord_iter(iter('abba'), Words('ab'), None, 4, None)
            sage: w = sage.words.word.FiniteWord_iter(iter('abba'), Words('ab'), 0, 4, 1)
        """
        super(FiniteWord_iter, self).__init__(parent)
        if stop is None:
            raise ValueError, "unspecified length on finite word"
        start = start or 0
        step = step or 1
        self.__it = islice(it, start, stop, step)
        self.__l = int((stop - start)/step)
    
    def _iter_syms(self):
        r"""
        TESTS:
            sage: from itertools import count, imap
            sage: list(Words('012345')(imap(str, count()), slice(1, 5))._iter_syms())
            ['1', '2', '3', '4']
        """
        new, self.__it = copy_it(self.__it)
        return new
    
    def __len__(self):
        r"""
        TESTS:
            sage: from itertools import count
            sage: len(Words(range(1, 5))(count(), slice(1, 5)))
            4
        """
        return self.__l
    
    def _get_val(self, i):
        r"""
        TESTS:
            sage: w = Words('ab')('abb', slice(3), format='iterator')
            sage: w._get_val(0)
            0
            sage: w._get_val(2)
            1
        """
        i = self._check_getitem_args(i)
        return self.parent().alphabet().to_int(islice(self, i, None).next())
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: from itertools import count, imap
            sage: w = Words('012345')(imap(str, count()), slice(6))
            sage: w[:]
            word: 012345
            sage: w[0:]
            word: 012345
            sage: w[10:]
            word: 
            sage: w[-2:]
            word: 45
            sage: w[-10:]
            word: 012345
            sage: w[:0]
            word: 
            sage: w[:2]
            word: 01
            sage: w[:10]
            word: 012345
            sage: w[:-1]
            word: 01234
            sage: w[:-10]
            word: 
            sage: w[::2]
            word: 024
            sage: w[::-2]
            word: 531
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[0]
            '0'
            sage: w[5]
            '5'
            sage: w[6]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: w[-1]
            '5'
            sage: w[-6]
            '0'
            sage: w[-7]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            if key.step < 0:
                return FiniteWord_list(slice_it(self._iter_syms(), len(self), key), self.parent())
            else:
                start, stop, step = slice_indices(key, len(self))
                return FiniteWord_iter(self._iter_syms(), self.parent(), start, stop, step)
        else:
            return islice(self, key, None).next()

class Word_conc(object):
    r"""
    Class that acts as a function to concatenate words.
    """
    def __init__(self, *w):
        r"""
        TESTS:
            sage: W = Words('ab')
            sage: fc = sage.words.word.Word_conc(W('abba'), W('baab'))
        """
        self.__l = tuple(w)
    
    def __call__(self, key):
        r"""
        Returns the character at position n in the word.
        
        EXAMPLES:
            sage: W = Words('ab')
            sage: fc = sage.words.word.Word_conc(W('abba'), W('baab'))
            sage: fc(1)
            'b'
            sage: fc(6)
            'a'
        """
        for i in xrange(len(self.__l)):
            if (key - len(self.__l[i]) < 0):
                return self.__l[i][key]
            key -= len(self.__l[i])
    
    def __len__(self):
        r"""
        Returns the length of the concatenation.
        
        TESTS:
            sage: W = Words('ab')
            sage: sage.words.word.Word_conc(W('abba'), W('baab')).__len__()
            8
        """
        return reduce(lambda s, w: s+len(w), self.__l, 0)

#######################################################################
#                                                                     #
#                          Infinite words                             #
#                                                                     #
#######################################################################

class InfiniteWord(GenericWord):
    def _repr_(self):
        r"""
        Returns a string representation of the object
        
        TESTS:
            sage: Words([0, 1])(lambda n: n%2)._repr_()
            'Infinite word over {0, 1}'
        """
        return "Infinite word over %r" % self.alphabet()

    def _check_getitem_args(self, key):
        r"""
        TESTS:
            sage: from sage.words.word import InfiniteWord
            sage: w = Words('')(str)
            sage: InfiniteWord._check_getitem_args(w, slice(-1))
            Traceback (most recent call last):
            ...
            ValueError: negative index on infinite word
            sage: InfiniteWord._check_getitem_args(w, slice(-1, None))
            Traceback (most recent call last):
            ...
            ValueError: negative index on infinite word
            sage: InfiniteWord._check_getitem_args(w, slice(None, None, -1))
            Traceback (most recent call last):
            ...
            ValueError: negative step and no defined start
            sage: InfiniteWord._check_getitem_args(w, slice(1))
            slice(None, 1, 1)
            sage: InfiniteWord._check_getitem_args(w, 1)
            1
            sage: InfiniteWord._check_getitem_args(w, -1)
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
        """
        key = super(InfiniteWord, self)._check_getitem_args(key)
        if isinstance(key, slice):
            if (key.start is not None and key.start < 0) or \
                (key.stop is not None and key.stop < 0):
                raise ValueError, "negative index on infinite word"
            if key.step is not None and key.step < 0 and key.start is None:
                raise ValueError, "negative step and no defined start"
            return key
        if key < 0:
            raise IndexError, "negative index on infinite word"
        return key

class InfiniteWord_func(InfiniteWord):
    def __init__(self, func, parent, start=None, step=None):
        r"""
        TESTS:
            sage: w = sage.words.word.InfiniteWord_func(lambda i: i%2, Words([0, 1]))
            sage: w = sage.words.word.InfiniteWord_func(lambda i: i%2, Words([0, 1]), 0, 1)
        """
        super(InfiniteWord_func, self).__init__(parent)
        if start is None and step is None:
            self.__func = func
        else:
            start = start or 0
            step = step or 1
            self.__func = lambda x: func(start + x * step)
    
    def _iter_syms(self):
        r"""
        Iterates over the symbols in the word (infinite).
        
        TESTS:
            sage: from itertools import islice
            sage: w = Words('ab')(lambda i: {False:'a', True:'b'}[i > 0])
            sage: list(islice(w._iter_syms(), 10))
            ['a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b']
        """
        for i in count():
            yield self.__func(i)
    
    def _get_val(self, i):
        r"""
        TESTS:
            sage: w = Words('ab')(lambda i: {False:'a', True:'b'}[i > 0])
            sage: w._get_val(0)
            0
            sage: w._get_val(42)
            1
        """
        i = self._check_getitem_args(i)
        return self.parent().alphabet().to_int(self.__func(i))
    
    def __getitem__(self, key):
        """
        sage: w = Words([0, 1, 2])(lambda x: x%3)
        sage: w[:]
        Infinite word over {0, 1, 2}
        sage: w[0:]
        Infinite word over {0, 1, 2}
        sage: w[1:]
        Infinite word over {0, 1, 2}
        sage: w[:0]
        word: 
        sage: w[:4]
        word: 0120
        sage: w[::2]
        Infinite word over {0, 1, 2}
        sage: w[::0]
        Traceback (most recent call last):
          ...
        ValueError: slice step cannot be zero
        sage: w[5]
        2
        """
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            if key.step < 0 or key.stop is not None:
                return FiniteWord_func(self.__func, self.parent(), key.start, key.stop, key.step)
            else:
                return InfiniteWord_func(self.__func, self.parent(), key.start, key.step)
        else:
            return self.__func(key)

class InfiniteWord_iter(InfiniteWord):
    def __init__(self, it, parent, start=None, step=None):
        r"""
        TESTS:
            sage: from itertools import chain, repeat
            sage: w = sage.words.word.InfiniteWord_iter(chain('a', repeat('b')), Words('ab'))
            sage: w = sage.words.word.InfiniteWord_func(chain('a', repeat('b')), Words('ab'), 0, 1)
        """
        super(InfiniteWord_iter, self).__init__(parent)
        if start is None and step is None:
            self.__it = iter(it)
        else:
            self.__it = islice(it, start, None, step)
    
    def _iter_syms(self):
        r"""
        TESTS:
            sage: from itertools import chain, repeat, islice
            sage: w = Words('ab')(chain('a', repeat('b')))
            sage: list(islice(w._iter_syms(), 10))
            ['a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b']
        """
        new, self.__it = copy_it(self.__it)
        return new
    
    def _get_val(self, i):
        r"""
        TESTS:
            sage: from itertools import chain, repeat
            sage: w = Words('ab')(chain('a', repeat('b')))
            sage: w._get_val(0)
            0
            sage: w._get_val(42)
            1
        """
        i = self._check_getitem_args(i)
        return self.parent().alphabet().to_int(islice(self, i, None).next())
    
    def __getitem__(self, key):
        """
        sage: from itertools import cycle
        sage: w = Words([0, 1, 2])(cycle([0, 1, 2]))
        sage: w[:]
        Infinite word over {0, 1, 2}
        sage: w[0:]
        Infinite word over {0, 1, 2}
        sage: w[1:]
        Infinite word over {0, 1, 2}
        sage: w[:0]
        word: 
        sage: w[:4]
        word: 0120
        sage: w[::2]
        Infinite word over {0, 1, 2}
        sage: w[::0]
        Traceback (most recent call last):
          ...
        ValueError: slice step cannot be zero
        sage: w[5]
        2
        """
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            if key.stop is not None:
                if key.step < 0:
                    return FiniteWord_iter(self._iter_syms(), self.parent(), key.stop, key.start, 1)[::key.step]
                else:
                    return FiniteWord_iter(self._iter_syms(), self.parent(), key.start, key.stop, key.step)
            else:
                return InfiniteWord_iter(self._iter_syms(), self.parent(), key.start, key.step)
        else:
            return islice(self, key, None).next()
